package com.example.array;

import java.util.Deque;
import java.util.LinkedList;

public class Leetcode678_CheckValidString {
    public static void main(String[] args) {
        String str = "(*)()";
        System.out.println(new Solution().checkValidString(str));
    }

    static class Solution {


        /**
         * 双栈
         * 定义两个栈:leftStack 存 '(' 所在位置的下标，starStack 存 '*' 所在位置的下标。
         *   1.当遇到 '(' 时，'(' 所在位置的下标入栈；当遇到 ' * ' 时，'*' 所在位置的下标入栈。
         *   2.当遇到 ')' 时，leftStack 中的栈顶元素出栈，
         *     若此时 leftStack 为空，则继续看 starStack 是否为空，
         *     若不为空则 starStack 栈顶元素出栈，若为空返回则 false (遇到了 ')'，
         *     但在这之前一个 '(' 和 '*' 都没遇到，则一定不会匹配)。
         *
         *   3.当字符串全部遍历完时，
         *     若 starStack 的长度比 leftStack 的长度要小，则返回 false (有剩余的 '('未被匹配完毕，则一定不会匹配)；
         *     否则，比较两个栈的栈顶元素值的大小，要保证 '(' 在 '*' 的左边(starStack.peek() > leftStack.peek())才能匹配成功，
         *     当遇到满足条件的栈顶元素时，栈顶元素出栈，继续比较下一个。只要有一次该条件不满足，则直接返回 false；否则，返回 true。
         *。
         * @param s
         * @return
         */
        private boolean checkValidString1(String s) {
            // 定义两个栈分别用于存放'('和'*'的索引
            Deque<Integer> leftStack = new LinkedList<>();
            Deque<Integer> starStack = new LinkedList<>();

            char[] chars = s.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                if (chars[i] == '(') { // 遇到 '(' 时
                    leftStack.push(i);
                } else if (chars[i] == '*') { // 遇到 ')' 时
                    starStack.push(i);
                } else {// 遇到 '*' 时
                    if (!leftStack.isEmpty()) {
                        leftStack.pop();
                    } else if (!starStack.isEmpty()) {
                        starStack.pop();
                    } else {
                        return false;
                    }
                }
            }

            if (leftStack.size() > starStack.size()) return false;

            while (!starStack.isEmpty() && !leftStack.isEmpty()) {
                if (starStack.peek() < leftStack.peek()) return false;
                starStack.pop();
                leftStack.pop();
            }
            return true;
        }

        public boolean checkValidString(String s) {
            return checkValidString1(s);
        }
    }
}
